package dp;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
 * author: Mr.Du
 * Date: 2023/4/6
 * Time: 21:25
 */
public class CountSubstrings {

    public static void main(String[] args) {
        int res = countSubstrings("abc");
        System.out.println(res);

    }

    static int res;

    public static int countSubstrings(String s) {
        for(int i = 0;i < s.length();i++){
            isP(s,i,i);
            isP(s,i,i+1);
        }
        return res;
    }


    // 中心扩散实现
    public static void isP(String s,int i,int j){
        while(i >=0 && j < s.length() && s.charAt(i) == s.charAt(j)){
            i--;
            j++;
            res++;
        }
    }


    // 动态规划实现
    public static int countSubstrings1(String s){
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        for(int i = 0;i < len;i++){
            dp[i][i] = true;
            res++;
        }

        for(int j = 1;j < len;j++){
            for(int i = 0;i < j;i++){
                if(s.charAt(i) != s.charAt(j)){
                    dp[i][j] = false;
                }else{
                    // 相等了，就是判断s[i + 1] 和 s[j - 1]
                    // 如果j - 1 和i + 1相差小于2，一定是回文，即1个字符
                    //  j - 1 - (i + 1) + 1 < 2    ===>   j - i < 3
                    if(j - i < 3){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if(dp[i][j]){
                    res++;
                }
            }

        }
        return res;
    }
}
